import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: dust
 * @Date: 2019/11/19 18:52
 */
class Solutiontwo {

    private int R;
    private int C;
    private int[][]dirs={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        R=grid.length;
        C=grid[0].length;
        boolean[][] visited=new boolean[R][C];
        int[][] dis=new int[R][C];

        if(grid[0][0]==1){
            return -1;
        }
        if(R==1&&C==1){
            return 1;
        }

        Queue<Integer> queue=new LinkedList<>();
        queue.add(0);
        visited[0][0]=true;dis[0][0]=1;
        while(!queue.isEmpty()){
            int cur=queue.remove();
            int curx=cur/C;
            int cury=cur%C;
            for(int d=0;d<8;d++){
                int nextx=curx+dirs[d][0];
                int nexty=cury+dirs[d][1];
                if(isArea(nextx,nexty)&&!visited[nextx][nexty]&&grid[nextx][nexty]==0){
                    visited[nextx][nexty]=true;
                    queue.add(nextx*C+nexty);
                    dis[nextx][nexty]=dis[curx][cury]+1;
                    if(nextx==R-1&&nexty==C-1){
                        return dis[nextx][nexty];
                    }
                }
            }
        }
        return -1;
    }

    private boolean isArea(int x,int y){
        return x>=0&&x<R&&y>=0&&y<C;
    }

}
